package BFS解决FloodFill算法;

import java.util.LinkedList;
import java.util.Queue;

public class test1 {
    // FloodFill算法: 这里用BFS来解决问题(宽搜)
    /**
     * FloodFill算法 --> 很经典 同时BFS今年也很重要,考的概率很高
     * 本质就是连通块
     */
    // 用数形矩阵来表示某一位置的上下左右
    int[] dx = {0,0,1,-1};
    int[] dy = {1,-1,0,0};
    public int[][] floodFill(int[][] image, int sr, int sc, int color) {
        int n = image.length,m = image[0].length;
        int prev = image[sr][sc]; // 这是当前被选中要进行变化的位置的元素,只有上下左右都是这个元素才能进行改变
        if(prev==color) return image; // 已经是要改成的结果,所以不需要进行变动

        Queue<int[]> queue = new LinkedList<>(); // 用一个队列来记录当前板块的边界点
        queue.add(new int[]{sr,sc});

        while(!queue.isEmpty()){
            int[] arr = queue.poll();// 将当前要进行处理的边界点拿出来,看看他是否能进行扩散
            int a=arr[0],b=arr[1];
            image[a][b] = color; // 进行转变
            for (int i = 0; i < 4; i++) { //一共有上下左右四个维度
                int x = a+dx[i];
                int y = b+dy[i];
                // 获取到上下左右,然后判定上下左右是否可以进行扩散,同时不能越界
                if(x<n&&x>=0&&y<m&&y>=0&&image[x][y]==prev)
                    queue.add(new int[]{x,y});
            }
        }
        return image;
    }
}
